ACLPC L
ACLPC_L
https://gyazo.com/b616e54f13c09c43d58d90950621c511
二値の列に対して(0の個数, 1の個数, 転倒数)を対応づける。
この値は、2つの列を結合したものについて計算することがこの値だけからできる
(DPを構築する時のような気持ち)
code::
f((a1, b1, c1), (a2, b2, c2)) = (a1 + a2, b1 + b2, c1 + c2 + b1 * a2)
これは落ち着いて考えれば当たり前
0の個数、1の個数に関しては単なる和
転倒数は、それぞれの元々の転倒数に、結合によって増える量を足す
この結合によって増える量とは「転倒してる数のペア」がそれぞれの列に分かれてるものの個数なので「左の列の中の1の個数」に「右の列の中の0の個数」をかけたものになる
この合成演算fは結合的であり単位元(0, 0, 0)を持つのでモノイドである よってこの値はセグメント木の値域に使うことができる
作用は列のビット反転だが、この時に値はどうなるか
(y, x, x * y - z)
異なる数値の組み合わせがx * yペアあって、うちzペアが転倒してる、反転させると残りが転倒ペアになる 余事象